# -*- coding: utf-8 -*-
"""
-------------------------------------------------
   File Name：     utils
   Description :
   Author :       Flyoung
   date：          2023/3/15
-------------------------------------------------
   Change Activity:
                   2023/3/15:
-------------------------------------------------
"""
from typing import Dict

from compiler.state_machine.lib import epsilon
from compiler.state_machine.state import State, StateDistributor


def construct_directed_graph(d_tran: Dict, n):
    """
    根据给定的字典，构造图
    :param d_tran:
    :param n:
    :return:
    """
    sd = StateDistributor()
    states = [sd.apply_state() for _ in range(n + 1)]
    for state_tag, edges in d_tran.items():
        s = states[states.index(state_tag)]
        for edge_label, next_nodes in edges.items():
            for next_node in next_nodes:
                next_node = states[states.index(next_node)]
                s.add_next_state(edge_label, next_node)
    return states


def epsilon_closure(t, close: bool = False):
    if t:
        if type(t) is not list:
            t = [t]
        added = set()
        stk = [i for i in t]
        while len(stk) > 0:
            top = stk.pop()
            for edge, state in top.next_states:
                if edge == epsilon and state not in added:
                    added.add(state)
                    stk.append(state)
        if close:
            added.update(t)
        return sorted(list(added))
    return t


def simplify_state_transition_table(d_tran_tmp, final_state):
    """
    状态转换表中状态替换成记号
    :param d_tran_tmp:
    :param final_state:
    :return: 简化后的状态图，简化状态对应的原始状态
    """
    d_tran = dict()
    d_tran_desc = dict()
    # 状态 : 输入
    for state_idx, sign_input in d_tran_tmp.items():
        state_type_ = chr(ord('A') + state_idx)
        d_tran_desc[state_type_] = [s.tag for s in final_state[state_idx]]
        d_tran[state_type_] = dict()
        for sign, convert_res in sign_input.items():
            # state 输入 sign 转移到状态 convert_res
            convert_res_ = chr(ord('A') + final_state.index(convert_res))
            if sign not in d_tran[state_type_]:
                d_tran[state_type_][sign] = []
            d_tran[state_type_][sign].append(convert_res_)
    return d_tran, d_tran_desc


def simplify_start_and_end_states(start_state, end_states, final_state):
    # 初始状态与接收状态的标记
    end_states_ = []
    for i, s in enumerate(final_state):
        try:
            if isinstance(start_state, State) and start_state in s:
                start_state = chr(ord('A') + i)
            for end_state in end_states:
                if end_state in s:
                    end_states_.append(chr(ord('A') + i))
        except Exception as e:
            print(e)
    return start_state, sorted(list(set(end_states_)))


def nfa2dfa(nfa, alphabet, start_state, end_states):
    """
    nfa 转换成 dfa
    :param end_states:
    :param start_state:
    :param nfa: 非确定有限状态自动机
    :param alphabet: 字母表
    :return:
    """
    d_tran = dict()
    final_state = list()
    t = epsilon_closure(nfa, close=True)
    stk = [t]
    # 还有未标记的集合
    while len(stk) > 0:
        t = stk.pop()
        if t not in final_state:
            final_state.append(t)
        # 标记状态对应的出边
        d_tran[final_state.index(t)] = dict()
        # 对字母表中的字符输入
        for char in alphabet:
            tmp = list()
            for s in t:
                nxt = s.move(char)
                # 转后后的 epsilon 闭包
                nxt_set = epsilon_closure(nxt, close=True)
                if nxt is not None:
                    tmp.extend(nxt_set)
            tmp = sorted(list(set(tmp)))
            if len(tmp) > 0:
                if tmp not in final_state:
                    final_state.append(tmp)
                    stk.append(tmp)
                d_tran[final_state.index(t)][char] = tmp

    start_state_, end_states_ = simplify_start_and_end_states(start_state, end_states, final_state)
    d_tran, d_tran_desc = simplify_state_transition_table(d_tran, final_state)
    return final_state, d_tran_desc, d_tran, start_state_, end_states_


def simplify_dfa(dfa, start_state, end_states, alphabet):
    """
    化简 DFA
    :param dfa:
    :param start_state:
    :param end_states:
    :param alphabet:
    :return:
    """

    def move(s, edge):
        # 对于状态 s 输入 edge, 输出转移后的状态
        if edge in dfa[s]:
            return dfa[s][edge]
        return None

    def simplify_move(final_states_, s, edge):
        # 简化后的 DFA 的状态转移
        next_node = move(s, edge)[0]
        for idx, states in enumerate(final_states_):
            if next_node in states:
                return chr(ord('A') + idx)
        return None

    def init_states_divide():
        # 初始状态集合划分
        start_states_, end_states_ = list(), list()
        for state_, convert_res in dfa.items():
            if state_ in end_states:
                end_states_.append(state_)
            else:
                start_states_.append(state_)

        return [sorted(start_states_), sorted(end_states_)]

    def get_final_states(total_):
        final_states_ = []
        while len(total_) > 0:
            t = total_.pop()
            if len(t) == 1:
                final_states_.append(t)
                continue
            for state in t:
                same_convert_states = []
                # 性质 : 对于所有的输入，转移后的状态与 state 保持一致
                for cmp_state in t:
                    for char in alphabet:
                        if state == cmp_state:
                            continue
                        if move(state, char) != move(cmp_state, char):
                            same_convert_states = []
                            break
                        else:
                            if cmp_state not in same_convert_states:
                                same_convert_states.append(cmp_state)
                # 若符合性质的状态数量 > 0
                if len(same_convert_states):
                    same_convert_states.append(state)
                    total_.append([i for i in t if i not in same_convert_states])
                    final_states_.append(same_convert_states)
        return final_states_

    def get_simplified_state_graph_express(final_states_):
        # 获取简化后的状态图表示
        d_tran = dict()
        d_tran_desc = dict()
        simplify_start, simplify_ends = None, []
        for idx, states in enumerate(final_states_):
            state = states[0]
            state_tag = chr(ord('A') + idx)
            convert_relation = dict()
            d_tran[state_tag] = convert_relation
            for char in alphabet:
                d = convert_relation[char] = convert_relation.get(char, [])
                d.append(simplify_move(final_states_, state, char))
            d_tran_desc[state_tag] = states
            if start_state in states:
                simplify_start = state_tag
            for end_state in end_states:
                if end_state in states and state_tag not in simplify_ends:
                    simplify_ends.append(state_tag)
        return d_tran, d_tran_desc, simplify_start, simplify_ends

    total = init_states_divide()
    final_states = sorted(get_final_states(total))
    is_simplified = len(final_states) != 0 and len(final_states) != len(dfa)
    return is_simplified, *get_simplified_state_graph_express(final_states)
